/*
 * @lc app=leetcode.cn id=1819 lang=typescript
 *
 * [1819] 序列中不同最大公约数的数目
 */

// @lc code=start
function countDifferentSubsequenceGCDs(nums: number[]): number {
  const gcd = (a: number, b: number) => (b === 0 ? a : gcd(b, a % b));
  const hash = new Map<number, number>();
  let max = 0;
  // 对nums数字去重并记录在hash中
  for (const num of nums) {
    max = Math.max(max, num);
    hash.set(num, 1);
  }

  let ans = 0;
  // 遍历，判断是否可以找到最大公约数是 i 的序列
  for (let i = 1; i <= max; i++) {
    let res = -1;
    // 对i的倍数且在hash中的数字求最大公约数
    for (let j = i; j <= max; j += i) {
      if (!hash.has(j)) continue;
      if (res === -1) {
        res = j;
      } else {
        res = gcd(res, j);
      }
    }
    // 结果等于 i，则说明可以找到最大公约数是 i 的序列
    if (res === i) ans++;
  }
  return ans;
}
// @lc code=end
